Back to course home
0% completed
Vote For New Content
Meta Hard Problems
Sliding Window Median (hard)
Solution: Sliding Window Median
Alien Dictionary (hard)
Solution: Alien Dictionary
Minimum Window Substring (hard)
Solution: Minimum Window Substring
Best Meeting Point (hard)
Solution: Best Meeting Point
Maximum Sum of 3 Non-Overlapping Subarrays (hard)
Solution: Maximum Sum of 3 Non-Overlapping Subarrays
Making A Large Island (hard)
Solution: Making A Large Island
Basic Calculator (Hard)
Solution: Basic Calculator
Serialize and Deserialize Binary Tree (hard)
Solution: Serialize and Deserialize Binary Tree
Longest Increasing Path in a Matrix (hard)
Solution: Longest Increasing Path in a Matrix
Valid Palindrome III (hard)
Solution: Valid Palindrome III
Lowest Common Ancestor of a Binary Search Tree (medium)
Problem Statement
Given a binary search tree (BST) and two of its nodes, find the node that is the lowest common ancestor (LCA) of the two given nodes. The LCA of two nodes is the node that lies in between the two nodes in terms of value and is the furthest from the root. In other words, it's the deepest node where the two nodes diverge in the tree. Remember, in a BST, nodes have unique values.
Examples
- Input:
- BST: [6,2,8,0,4,7,9,null,null,3,5]
- Node 1: 2
- Node 2: 8
- Expected Output: 6
- Justification: The nodes 2 and 8 are on the left and right children of node 6. Hence, node 6 is their LCA.
- Input:
- BST: [6,2,8,0,4,7,9,null,null,3,5]
- Node 1: 0
- Node 2: 3
- Expected Output: 2
- Justification: The nodes 0 and 3 are on the left and right children of node 2, which is the closest ancestor to these nodes.
- Input:
- BST: [6,2,8,0,4,7,9,null,null,3,5]
- Node 1: 4
- Node 2: 5
- Expected Output: 4
- Justification: Node 5 is the right child of node 4. Hence, the LCA is node 4 itself.
Constraints:
- The number of nodes in the tree is in the range [2, 105].
- -109 <=
Node.val<= 109 - All
Node.valare unique. p != qpandqwill exist in the BST.
Try it yourself
Try solving this question here:
Java
Saved to Cloud
. . . .
Solution: Simplify Path
Solution: Lowest Common Ancestor of a Binary Search Tree
Mark as Completed
On this page
Problem Statement
Examples
Try it yourself